package com.chb.stack;

/**
 算法思路
 1、数栈、符号栈
 2、遍历表达式
    如果是数、直接入数栈
    如果是符号
        如果符号栈为空，则直接入符号栈
        否则： 与符号栈内的符号比较（符号优先级）
            如果当前符号的优先级小于或等于栈中的符号，则从数栈中弹出两个数，符号栈中弹出一个符号， 进行运算，将得到的结果入数栈
            如果当前符号优先级大于 栈中符号，直接入符号栈
 3、当表达式遍历完，顺序的从数栈和符号栈pop出相应的数字和符号，进行运算
 4、最后在数栈中只有一个数字，就是表达式的结果。

 原文链接：https://chbxw.blog.csdn.net/article/details/106064702
 */
public class Calculator {
    public static void main(String[] args) {
        String expression = "3*40*5+3-4/2";


    }

    public static void testInfix(String expression) {
        MyStack2 numStack = new MyStack2(30);   // 数栈
        MyStack2 operStack = new MyStack2(10);  // 符号栈

        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int index = 0; // 符号的索引

        // 算法思路的具体实现
        boolean preNum = false; // 标记前一个字符是否是数字
        for (int i=0; i< expression.length(); i++) {
            char c = expression.substring(i, i+1).charAt(0);
            if (operStack.isOper(c))  { // 符号
                preNum = false;
                if (operStack.isEmpty()) { // 符号栈为空
                    operStack.push(c);
                } else {
                    int charTop = operStack.peek(); // 符号栈的栈顶
                    if (operStack.priority(c) <= operStack.priority(charTop)) {
                        num2 = numStack.pop();
                        num1 = numStack.pop();
                        oper = operStack.pop();
                        int ret = numStack.cal(num1, num2, oper);
                        // 结果入数栈
                        numStack.push(ret);
                        operStack.push(c);
                    } else {
                        operStack.push(c);
                    }
                }
            } else { //数字
                // 累加数值
                int sum = c - 48;
                if (preNum) {
                    sum += numStack.pop() * 10;
                }
                numStack.push(sum);
                preNum = true;
            }
        }


        while (!operStack.isEmpty()) {
            num2 = numStack.pop();
            num1 = numStack.pop();
            oper = operStack.pop();
            int ret = numStack.cal(num1, num2, oper);

            // 结果入数栈
            numStack.push(ret);
        }
        System.out.println(expression + "=" + numStack.pop());
    }

}


/**
 * 使用数据模拟栈
 *
 */
class MyStack2 {
    private int capacity;
    private int[] data;
    private int top = -1; // 栈顶的位置

    public MyStack2(int initCapacity) {
        this.capacity = initCapacity;
        data = new int[this.capacity];
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(int value) {
        if (isFull()) {
           throw new RuntimeException("栈满");
        } else {
            top++;
            data[top] = value;
        }
    }

    // 出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int retVal = data[top];
        top--;
        return retVal;
    }
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        return data[top];
    }

    // 展示
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <= top; i++) {
            System.out.printf("stack[%d]=%d,", i, data[i]);
        }
        System.out.println();
    }


    /**
     * 判断 运算符 的优先级
     * @param oper
     * @return
     */
    public int priority(int oper) {
        if (oper == '+' || oper == '-') {
            return  0;
        } else if (oper == '*' || oper == '/') {
            return  1;
        } else {
            return -1; // 暂时默认只有 +、—、*、/
        }
    }

    /**
     * 判断是否是操作符
     * @param c
     * @return
     */
    public boolean isOper(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    /**
     * 运算
     * @param num1 第一个数字
     * @param num2 第二个数字
     * @param oper 操作符
     * @return
     */
    public int cal(int num1, int num2, int oper) {
        int ret = 0; // 运算结果
        switch (oper) {
            case '+':
                ret = num1 + num2;
                break;
            case '-':
                ret = num1 - num2;
                break;
            case '*':
                ret = num1 * num2;
                break;
            case '/':
                ret = num1 / num2;
                break;
            default:
                break;
        }
        return ret;
    }
}
